1. Field of the Invention
The present invention relates very broadly to computers, and generally to an inference engine used in knowledge base development shells and knowledge based application programs (expert systems). The present invention relates more particularly to an inference engine device and method thereof that integrates backward chaining with Rete based forward chaining.
2. Related Art
Knowledge based application programs (expert systems) generally comprise a knowledge base and an inference engine. The inference engine is that part of the system that "reasons." Two inferencing strategies that have been employed by expert systems are backward chaining and forward chaining.
Backward chaining was one of the first inferencing strategies used in expert systems. Backward chaining has proven its usefulness for classification problem solving. Backward chaining is also one of the first clearly-defined inferencing strategies to be used in reusable expert system shells. One such expert system is known as MYCIN. The MYCIN system is fully explained in Van Melle, W., Scott, A. C., Bennet, J. S., Peairs, M. A. The EMYCIN Manual. Heuristic Programming Project Report HPP-81-16. Stanford University. 1981. This reference is hereby incorporated by reference into this specification in its entirety.
Systems of the type exemplified by MYCIN, use backward chaining to focus processing along a single line of reasoning towards a goal selected by the system. Its power as a general inferencing strategy soon became apparent, and was implemented as the primary inferencing strategy in such expert system development shells as EMYCIN, S.1, and Expert Systems Environment. An expert system development shell is a system that allows a user to build a wide variety of expert systems.
Backward chaining is a depth-first search strategy of decision tree traversal. Because it is depth-first, it has the primary characteristic of focusing inferencing along reasoning paths until an answer is reached.
Its focused inferencing has a number of side benefits. First, questions seem to be asked in a logical order, indicating to the user that the system is working towards a goal along a specific path of reasoning. Second, backward chaining inherently provides a convenient way of producing both the current line of reasoning that the system is pursuing and the line of reasoning that caused a particular value to be concluded.
Classical backward chaining generally operates as follows:
Given a Goal (an object for which a value is desired),
1. Collect all of the rules that can be activated (not already false) and if activated will provide the desired object value; PA1 2. Select a rule from the collection of relevant rules (based on some selection criteria); and PA1 3. If object values are needed to activate the rule then make the next needed object the new goal and start the above process over. Otherwise, activate the rule. PA1 1. Perform matching of the rules against the data known to the system creating in the conflict set a rule instance for each rule and a set of data that meets the rule's conditions; PA1 2. Perform conflict resolution on the rule instances in the conflict set until no rule instances are left; PA1 3. Commence backward chaining when the conflict set is empty by selecting an available goal; PA1 4. Initial goal expansion using backward chaining if the goals have been established; PA1 5. Distribute backward chaining data through the Rete network as goals are expanded (rule instances may appear in the conflict set); PA1 6. Resume forward chaining if the rule instances appear in conflict set, and continue such forward chaining until conflict set is empty; PA1 7. Resume backward chaining when the conflict set is empty; and/or PA1 8. Return control to the software calling (controlling or commanding) the knowledge base when both the conflict set is empty and there are no more goals to pursue.
Often as a function of step 1, conventional systems will ask the user to provide the value of the object as an alternative to pursuing rules to get the value.
Another form of backward chaining is that performed by a PROLOG based system. The PROLOG system is fully explained in Clocksin, W. F. and C. S. Mellish, Programming in Prolog, Berlin: Springer-Verlag. 1984. This reference is hereby incorporated by reference in its entirety into this specification.
PROLOG is in essence a complete programing language based on resolution theorem proving. In PROLOG predicates are searched that match the pattern established as the current goal.
There are two apparent differences between PROLOG's backward chaining and classical backward chaining. First, PROLOG may establish as a goal the acquisition of either any value or a specific value. This is opposed to classical backward chaining where any value will accomplish the goal. Second, PROLOG has a feature called backtracking, that allows predicates established as part of the backward chaining process to be retracted if the search path leads to a dead end. This is a significant feature of PROLOG.
While backward chaining has proven to be a simple and easy to use inferencing method, it is not ideal for all problem types. Problems for which the solution must be synthesized from available data, such as monitoring, scheduling, and design problems are difficult to perform with backward chaining. Problems which require the monitoring of constantly changing data can be difficult or inefficient to solve with a backward chaining paradigm or approach. These types of problems can often be easily solved with a forward chaining approach, especially that based on the Rete pattern matching algorithm. The Rete pattern matching algorithm is well known in the art. The Rete pattern matching algorithm is fully explained in Forgy, C. L. "Rete: A Fast Algorithm for the Many Pattern/Many Object Match Problem", Artificial Intelligence, 1982. This reference is hereby incorporated by reference in its entirety into this specification.
In addition, as expert system applications are moved from the realms of research and novelty applications to serious deployable applications, emphasis has shifted towards performance and embedability. Embedability means the ability of the expert system to be embedded (sub-component) of a standard application program.
To meet these demands, forward chaining has become the inferencing strategy of choice in many applications. Forward chaining has the ability to deal with a non-monotonic and changing fact base, and operate with high performance (using, for example, a Rete network to store partial inferences). As applications have become tightly integrated with existing systems, asking questions of the user has shifted to searching databases.
Such applications, however, do not eliminate the need for backward chaining. Tight focusing on particular reasoning paths is still valuable for certain diagnostic applications among others. It is still beneficial to ask users questions in an intelligent manner, even if such questions are less frequent. In addition, the highly focused reasoning of backward chaining can be more efficient than forward chaining for some applications.
Most real world problems are not of a single problem type, but are a collection of sub-problems. Thus, many of these problems require a mixture of paradigms or inferencing approaches in order to solve the sub-problems. In addition, a mixture of both paradigms in a tightly coupled approach, sometimes called mixed chaining or opportunistic reasoning, is needed for some problems.